{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 六、 图\n",
    "\n",
    "## 图的概述\n",
    "\n",
    "图 **graph** 定义为 G=(V,E)，其中集合 V 中的元素称作顶点 **vertex**，集合 E 中的元素分别对应于 V 中的某一对顶点 (u, v)，表示它们之间的某种关系，称为边 **edge**。\n",
    "\n",
    "若边 (u,v) 所对应的顶点 u 和 v 的次序无所谓，则称为无向边 **undirected edge**，例如同学关系; 否则为有向边 **directed edge**，例如企业与银行间的借贷关系。\n",
    "\n",
    "有向边 (u,v) 中的 u 称为边的起点 **origin** 或尾顶点 **tail**，而 v 为终点 **destination** 或头顶点 **head**。\n",
    "\n",
    "由无向边组成的图为无向图 **undirected graph, undigraph**，由有向边组成的为有向图 **directed graph, digraph**，混合组成的为混合图 **mixed graph**。\n",
    "\n",
    "![graph_3_forms.png](img/c6_graph/graph_3_forms.png)\n",
    "\n",
    "有向图更通用，因为无向边可以等价转化成两条有向边。故重点研究有向图。\n",
    "\n",
    "## 度\n",
    "\n",
    "边 e=(u,v) 中，称 u 和 v 彼此邻接 **adjacent**，互为邻居; 而顶点都与边 e 彼此关联 **incident**。无向图中，与顶点 v 关联的边数为 v 的度数 **degree, deg(v)**。而有向边中，边 e 称为 u 的出边 **outgoing edge** 和 v 的入边 **incoming edge**。v 的出边总数称为其出席 **out-degree, outdeg(v)**，入边总数称为其入度 **in-degree, indeg(v)**。\n",
    "\n",
    "## 简单图\n",
    "\n",
    "联接于同一顶点之间的边，称为自环 **self-loop**。不含任何自环的图称为简单图 **simple graph**，为主要研究对象。\n",
    "\n",
    "## 通路与环路\n",
    "\n",
    "+ 通路或路径 **path** 就是由 m+1 个顶点和 m 条边交替而成的一个序列，边的总数 m 称为通路的长度。\n",
    "+ 一条通路中，如果没有重复的顶点，称为简单通路 **simple path**。\n",
    "+ 起点和终点相同的通路称为环路 **cycle**。\n",
    "+ 不含任何环路的有向图称为有向无环图 **directed acyclic graph, DAG**。\n",
    "+ 除起止点节，再没有其它重复顶点的环路称为简单环路 **simple cycle**。\n",
    "+ 经过图中各边一次且恰好一次的环路称为欧拉环路 **Eulerian tour**，其长度为图中边的总数。\n",
    "+ 经过图中各顶点一次且恰好一次的环路，称为哈密尔顿环路 **Hamilton tour**。\n",
    "+ 各边带权重 **weight** 的图为带权图 **weighted graph** 或带权网络 **weighted network**。\n",
    "\n",
    "![cycle_instances.png](img/c6_graph/cycle_instances.png)\n",
    "\n",
    "## 复杂度\n",
    "\n",
    "应以顶点数与边数的总和 (n+e) 来度量。\n",
    "\n",
    "无论有多少顶点，边数都有可能为 0。考虑最多有多少边的情况：\n",
    "\n",
    "+ 当为无向图时，每一对顶点贡献一条边，n 个顶点时，第一个顶点可与其后 n-1 个顶点可联边，第二个顶点可与其后 n-2 个顶点联边，...，总数为 $(n-1)+(n-2)+\\cdots+1 = n(n-1)/2$。\n",
    "+ 当为有向图时，每一对顶点贡献两条边，总数为 n(n-1)。\n",
    "\n",
    "因此，边数 $e=O(n^2)$。\n",
    "\n",
    "\n",
    "# 邻接矩阵 adjacency matrix\n",
    "\n",
    "![adjacency_matrix.png](img/c6_graph/adjacency_matrix.png)\n",
    "\n",
    "n 个顶点的图用 `A[n][n]` 方阵表示，其中的每个单元描述顶点间的邻接关系，例如无权图用 1, 0 表示有无连接，有权图描述权重。\n",
    "\n",
    "\n",
    "## 时间性能\n",
    "\n",
    "对应于向量的 \"循秩访问“，图 ADT 中的所有静态操作接口及边的动态操作（插入和删除）都为 O(1)，但代价空间冗余（无向图中 `E[i][j]` 和 `E[j][i]` 的值相等）。\n",
    "\n",
    "顶点的插入和删除 O(n)。\n",
    "\n",
    "## 空间性能\n",
    "\n",
    "边集向量 `E[][]` 为 $O(n^2)$，而无向图的邻接矩阵必为对称阵，近一半冗余。\n",
    "\n",
    "\n",
    "# 邻接表 adjacency list\n",
    "\n",
    "邻接矩阵法的 $O(n^2)$ 空间性能待改进，特别在平面图（没有跳线的图）之类的稀疏图（sparse graph) 中，边数渐进地不超过 O(n)，仅与顶点总数大致相当。\n",
    "\n",
    "![adjacency_list.png](img/c6_graph/adjacency_list.png)\n",
    "\n",
    "## 复杂度\n",
    "\n",
    "邻接表所含列表数等于顶点总数 n,每条边在其中仅存一次（有向图）或两次（无向图），故空间总量为 O(n+e)，与图规模相当。\n",
    "\n",
    "但时间性能降低，例如  `exits(v, u)` 需在 v 对应的邻接表中顺序查找，O(n)。\n",
    "\n",
    "顶点的插入为 O(1),而非 O(n)，顶点删除为 O(e)。\n",
    "\n",
    "邻接表访问将同一顶点的所有关关联起来，有益于批量访问（这是图遍历等算法的典型处理流程和模式）。\n",
    "\n",
    "# 图的遍历\n",
    "\n",
    "**对所有顶点和边访问一次且仅一次**，是将图的非线性结构转化为半线性结构（遍历树）的过程。\n",
    "\n",
    "经遍历而确定的边类型中，最重要的一类即所谓的树边，它们与所有顶点共同构成了原图的一棵支撑树（森林），称为**遍历树 traversal tree**。\n",
    "\n",
    "图中顶点之间可能存在多条通路，故为避免对顶点的重复访问，在遍历中常要动态地设置各顶点不同的状态，并随着遍历的进程不断转换，直到最后的访问完毕。\n",
    "\n",
    "图的遍历更加强调对于特定状态顶点的甄别与查找，故也称为 **图搜索 graph search**。\n",
    "\n",
    "深度优先、广度优先、最佳优先等典型图搜索都能在线性时间内完成，即 O(n+e)，已是最优了。\n",
    "\n",
    "以下复杂度分析都以邻接表实现为基础。\n",
    "\n",
    "\n",
    "## 广度优先搜索\n",
    "\n",
    "图搜索的每一步迭代，通常都是选取某个已访问顶点的邻居。同一顶点的所有连接顶点之间的优先级，在多数遍历中都不讲究，因此实质的差异都体现在，当有多个顶点已被访问过后，应优先从谁的邻居中选取下一个顶点。\n",
    "\n",
    "**广告优先搜索 breath-first search, BFS** 策略：**越早被访问到的顶点，其邻居越优先被选用**。\n",
    "\n",
    "过程为先访问图顶点 s，再依次访问 s 所有尚未访问到的邻居;再按后者被访问的先后次序，逐个访问它们的邻居，如此不断。在所有已访问到的顶点中，仍有邻居尚未访问者，构成所谓的 **波峰集 frontier**，于是 BFS 等效为： **反复从波峰集中找到最早被访问到的顶点 v，若其邻居均已访问到，则将其逐出波峰集; 否则随意选出一个尚未访问的邻居，并将其加入到波峰集中**。\n",
    "\n",
    "类似树的层次遍历，波峰集中顶点的深度始终相差不超过 1。\n",
    "\n",
    "每次迭代都有一个顶点被访问，故至多迭代 O(n)。因不会遗漏每个刚被访问顶点的任何邻居，故对于无向图必能覆盖 s 所属的 **连通分量 connected component**，对于有向图必能覆盖以 s  为起点的 **可达分量 reachable component**。\n",
    "\n",
    "```cpp\n",
    "template <typename Tv, typename Te> //广度优先搜索 BFS 算法（全图）\n",
    "void Graph<Tv, Te>::bfs(int s) { //assert: 0 <= s < n\n",
    "    //初始化\n",
    "    reset();\n",
    "    int clock = 0;\n",
    "    int v = s; \n",
    "\n",
    "    do //逐一检查所有顶点\n",
    "        if (UNDISCOVERED == status(v) ) //一旦遇到尚未发现的顶点\n",
    "            BFS(v, clock); //即从该顶点出发启动一次 BFS\n",
    "    while ( s != (v=(++v%n)) ); //按序号检查，故不漏不重\n",
    "}\n",
    "\n",
    "template <typename Tv, typename Te> //广度优先搜索 BFS 算法（单个连通域）\n",
    "void Graph<Tv, Te>::BFS(int v, int& clock) { //assert: 0 <= v < n\n",
    "    Queue<int> Q; //引入辅助队列\n",
    "\n",
    "    status(v) = DISCOVERED; Q.enqueue(v); //初始化起点\n",
    "\n",
    "    while(!Q.empty()) {\n",
    "        int v = Q.dequeue();\n",
    "        dTime(v) == ++clock; //取出队首顶点 v\n",
    "        for (int u=firstNbr(v); -1<u; u=nextNbr(v, u)) //枚举 v 的所有邻居 u\n",
    "            if (UNDISCOVERED == status(u)) { //若 u 尚未被发现，则\n",
    "                status(u) == DISCOVERED; Q.enqueue(u); //发现该顶点\n",
    "                type(v, u) = TREE; parent(u) = v; //引入树边拓展支撑树\n",
    "            } else { //若 u 已被发现，或者甚至已访问完成，则\n",
    "                type(v, u) = CROSS; //将 (v, u) 归类于跨边\n",
    "            }\n",
    "\n",
    "        status(v) = VISITED; //至此，当前顶点访问完毕\n",
    "    }\n",
    "}\n",
    "```\n",
    "\n",
    "`BFS(s, clock)` 完成顶点 s 的连通或可达域的遍历，并标记出一棵遍历树 **BFS tree**。\n",
    "\n",
    "`bfs()` 后，将标记出一个 BFS 树的一个森林， **BFS forest**。\n",
    "\n",
    "![BFS_instance.png](img/c6_graph/BFS_instance.png)\n",
    "\n",
    "\n",
    "### BFS 复杂度\n",
    "\n",
    "空间复杂度： 顶点辅助队列 O(n) + 顶点状态 O(n) + 边状态 O(e) = O(n+e)。\n",
    "\n",
    "时间复杂度： 复位 O(n+e)，bsf() 枚举 O(n)，BFS() 中遍历每条边和每个顶点 O(n+e)，故部类为 O(n+e)。\n",
    "\n",
    "### BFS 应用\n",
    "\n",
    "基于 BFS 搜索，可有效解决连通域分解，最短路径问题。\n",
    "\n",
    "\n",
    "## 深度优先搜索 \n",
    "\n",
    "\n",
    "**深度优先搜索 depth-first search, DFS** 策略： **优先选取最后一个被访问到的顶点的邻居**。\n",
    "\n",
    "各顶点被访问到的次序，类似于树的先序遍历; 而各顶点被访问完毕的次序，则类似于树的后序遍历，从内到外一个个环遍历。\n",
    "\n",
    "![BFS_search.png](img/c6_graph/BFS_search.png)\n",
    "\n",
    "\n",
    "```cpp\n",
    "template <typename Tv, typename Te> //深度优先搜索 DFS 算法（全图）\n",
    "void Graph<Tv, Te>::dfs(int s) { //assert: 0 <= s < n\n",
    "    //初始化\n",
    "    reset();\n",
    "    int clock = 0;\n",
    "    int v = s; \n",
    "\n",
    "    do //逐一检查所有顶点\n",
    "        if (UNDISCOVERED == status(v) ) //一旦遇到尚未发现的顶点\n",
    "            DFS(v, clock); //即从该顶点出发启动一次 DFS\n",
    "    while ( s != (v=(++v%n)) ); //按序号检查，故不漏不重\n",
    "}\n",
    "\n",
    "template <typename Tv, typename Te> //深度优先搜索 DFS 算法（单个连通域）\n",
    "void Graph<Tv, Te>::DFS(int v, int& clock) { //assert: 0 <= v < n\n",
    "    dTime(v) = ++clock; //发现时间\n",
    "    status(v) = DISCOVERED; //发现当前顶点 v\n",
    "\n",
    "    for (int u=firstNbr(v); -1<u; u=nextNbr(v, u)) //枚举 v 的所有邻居 u\n",
    "        switch( status(u) ) { //并视其状态分别处理\n",
    "            case UNDISCOVERED: //u 尚未发现，意味着支撑树可在此拓展\n",
    "                type(v, u) = TREE;\n",
    "                parent(u) = v;\n",
    "                DFS(u, clock);\n",
    "                break;\n",
    "            case DISCOVERED: //u 已被发现但尚未访问完毕，此处有一个有向环路，应属被后代指向的祖先                            \n",
    "                type(v, u) = BACKWARD;\n",
    "                break;\n",
    "            default: //u 已访问完毕(VISITED, 有向图)，则视承袭关系分为前向边或跨边，\n",
    "                     // 比对活跃期，判定在 DFS 树中 v 是否为 u 祖先，若是，则边 (v,u) 是前向边，否则\n",
    "                     // 二者必然来自相互独立的两个分支，边 (v,u) 应归类为跨边 CROSS\n",
    "                type(v, u) = ( dTime(v) < dTime(u) ) ? FORWARD : CROSS;\n",
    "                break;\n",
    "        }\n",
    "\n",
    "    status(v) = VISITED; //至此，当前顶点 v 方告访问完毕\n",
    "    fTime(v) = ++clock; // 完毕时间\n",
    "}\n",
    "```\n",
    "\n",
    "这里为每个顶点 v 都记录了被发现的时刻 dTime 和访问完毕的时刻 fTime，对应的区间 [dTime(v), fTime(v)] 称为 v 的活跃期 **active duration**。 实际上，任意顶点 v 和 u 间是否存在祖先/后代关系，完全取决于二者的活跃期是否相互包含。\n",
    "\n",
    "![DFS_parent_child.png](img/c6_graph/DFS_parent_child.png)\n",
    "\n",
    "### 复杂度\n",
    "\n",
    "空间上：各顶点的时间标签和状态标记，以边各边的分类标记，为 O(n)+O(e)=O(n+e)\n",
    "\n",
    "时间复杂度为 O(n+e)。\n",
    "\n",
    "### 应用\n",
    "\n",
    "深度优先搜索是最重要的图遍历算法，是一个算法框架。\n",
    "\n",
    "## 拓扑排序 topological sorting\n",
    "\n",
    "将有向图中的所有顶点按“相容”原则排成一个线性序列。\n",
    "\n",
    "![topological_sorting.png](img/c6_graph/topological_sorting.png)\n",
    "\n",
    "+ 上图中，顶点 A 和 B 互换后依然是一个拓扑排序，故同一有向图的拓扑排序未必唯一。\n",
    "+ 在 (b) 中引入从 F 到 B 的边，构成一个有向环路，则不可能得到一个 “相容” 的线性序列，故拓扑排序未必存在。\n",
    "+ 但是有向无环图一定存在拓扑排序，反之，拓扑排序必然对应一个有向无环图。\n",
    "\n",
    "\n",
    "### 算法 1\n",
    "\n",
    "![topo_sort1.png](img/c6_graph/topo_sort1.png)\n",
    "\n",
    "从图 G 中找出入度为 0 的某个顶点 m，将其放入辅助栈中，并将 m 及其边从 G 中删除，之后剩下的图 G‘ 也是一个有向无环图，也有拓扑排序。从递归来看，一旦得到了 G’ 的拓扑排序，只需将 m 作为最小顶点插入，即可得图 G 的拓扑排序。\n",
    "\n",
    "\n",
    "### 算法 2 基于 DFS\n",
    "\n",
    "在深度优先搜索过程中，首先因访问完成而转换到 VISITED 状态的顶点 m，必然是出度为 0 的顶点，该顶点在此后的搜索过程中也不再起任何作用，于是下一转换至 VISITED 状态的顶点也可等效地理解为是从图中剔除 m （及其边）之后的出度为 0 者，在拓扑排序中，该顶点应为顶点 m 的前驱。DFS 搜索过程中各顶点被标记为 VISITED 的次序，恰好（逆序）给出了原图的一个拓扑排序。此外，DFS 搜索中一旦发现有边为 BACKWARD，则表示有环路，从而可立即终止算法并报告 “因非 DAG 而无法拓扑排序。\n",
    "\n",
    "```cpp\n",
    "template <typename Tv, typename Te> //基于 DFS 的拓扑排序算法\n",
    "Stack<Tv>* Graph<Tv, Te>::tSort_DFS(int s) { //assert: 0 <= s < n\n",
    "    reset();\n",
    "    int clock = 0;\n",
    "    int v = s;\n",
    "    Stack<Tv>* S = new Stack<Tv>; //用栈记录排序顶点\n",
    "\n",
    "    do {\n",
    "        if (UNDISCOVERED == status(v))\n",
    "            if (!TSort_DFS(v, clock, S)) { // clock 并非必需\n",
    "                while (!S->empty()) //任一连通域（亦即整图）非 DAG，则不必继续计算，直接返回\n",
    "                    S->pop();\n",
    "                break;\n",
    "            }\n",
    "    } while (s != (v=(++v % n)));\n",
    "\n",
    "    return S; //若输入为 DAG，则 S 内各顶点自顶向底排序; 否则（不存在拓扑排序），为空\n",
    "}\n",
    "\n",
    "template <typename Tv, typename Te> //基于 DFS 的拓扑排序算法（单趟）\n",
    "bool Graph<Tv, Te>::TSort_DFS(int v, int& clock, Stack<Tv>* S) { //assert: 0 <= v < n\n",
    "    dTime = ++clock;\n",
    "    status(v) = DISCOVERED; //发现顶点 v\n",
    "    for (int u=firstNbr(v); -1 < u; u = nextNbr(v, u)) //枚举 v 所有邻居 u\n",
    "        switch(status(u)) { //并视 u 的状态分别处理\n",
    "            case UNDISCOVERED:\n",
    "                parent(u) = v;\n",
    "                status(v, u) = TREE;\n",
    "                if (!TSort_DFS(u, clock, S)) //从顶点 u 处出发深入搜索\n",
    "                    return false; //若 u 及其后代不能拓扑排序（则全图也如此）\n",
    "                break;\n",
    "            case DISCOVERED:\n",
    "                status(v, u) = BACKWARD; //一旦发现后向边（非 DAG），则\n",
    "                return false; //不必深入\n",
    "            default: //VISITED (digraphs only)\n",
    "                status(v, u) = (dTime(v) < dTime(u)) ? FORWARD : CROSS;\n",
    "                break;\n",
    "        }\n",
    "\n",
    "    status(v) = VISITED;\n",
    "    S->push(vertex(v)); //顶点被标记为 VISITED; 并入栈\n",
    "    return true; //v 及后代可拓扑排序\n",
    "}\n",
    "```\n",
    "\n",
    "复杂度都为 O(n+e)。\n",
    "\n",
    "\n",
    "## 双连通域分解\n",
    "\n",
    "![bi-connected-component.png](img/c6_graph/bi-connected-component.png)\n",
    "\n",
    "无向图中，若删除顶点 v 后所包含的连通域增多，则 v  称为切割节点 **cut vertex** 或 关节点 **articulation vertex**。如上面 6.13 中的关节点。关节点在网络系统中对应于网关，因此很重要。\n",
    "\n",
    "不含任何关节点的图称作双连通图。\n",
    "\n",
    "任一无向图都可视作由若干个极大的双连通子图组合而成，这样的每一个子图都称作原图的一个双连通域 **bi-connected component**。\n",
    "\n",
    "### 双连通域分解算法\n",
    "\n",
    "关节点删除后，图中的双连通域会增加。\n",
    "\n",
    "+ 叶节点： 在 DFS 树中，叶节点绝不可能是原图中的关节点，此类顶点的删除即不影响 DFS 树的连通性，也不影响原图的连通性。\n",
    "+ 根节点： 若 DFS 树的根节点有至少两个分支，则必为一个关节点。\n",
    "+ 内部节点： 如下图中，若节点 C 的移除导致其某一真子树（如 D 为根的树）与其真祖先之间无法连通，则 C 必为关节点。反之，若 C 的所有真子树都能与 C 的某一真祖先连通，则 C 就不可能为关节点。在无向图的 DFS 树中， C 的真子树只能通过 **backward** 边与 C 的真祖先连通。因此，只要在 DFS 搜索中记录并更新各顶点 v 所能（经由 backward 边）连通的最高祖先(highest connected ancestor, HAC)，即可及时认定关节点。\n",
    "\n",
    "![inner_articulation_vertex.png](img/c6_graph/inner_articulation_vertex.png)\n",
    "\n",
    "```cpp\n",
    "template <typename Tv, typename Te>\n",
    "void Graph<Tv, Te>::bcc(int s) { //基于 DFS 的 BCC 分解算法\n",
    "    reset();\n",
    "    int clock = 0;\n",
    "    int v = s;\n",
    "    Stack<int> S; //栈 S 用于记录已访问的顶点\n",
    "\n",
    "    do \n",
    "        if (UNDISCOVERED == status(v)) { //一旦找到有未发现的顶点（新连通分量）\n",
    "            BCC( v, clock, S); //即从该顶点出发启动一次 BCC\n",
    "            S.pop(); //遍历返回后，弹出栈中最后一个顶点---当前连通域的起点\n",
    "        }\n",
    "    while ( s != (v=(++v % n)) );\n",
    "}\n",
    "\n",
    "#define hca(x) (fTime(x)) //利用此处闲置的 fTime[] 充当 hca[]\n",
    "\n",
    "template <typename Tv, typename Te>\n",
    "void Graph<Tv, Te>::BCC(int v, int& clock, Stack<int>& S) {\n",
    "    hca(v) = dTime(v) = ++clock;\n",
    "    status(v) = DISCOVERED;\n",
    "    S.push(v); // v 被发现并入栈\n",
    "    for (int u = firstNbr(v); -1 < u; u = nextNbr(v, u)) //枚举 v  的所有邻居 u\n",
    "        switch( status(u) ) { //并视 u 的状态分别处理\n",
    "            case UNDISCOVERED:\n",
    "                parent(u) = v;\n",
    "                type(v, u) = TREE;\n",
    "                BCC(u, clock, S); //从顶点 u 处深入\n",
    "\n",
    "                if (hca(u) < dTime(v)) //遍历返回后，若发现 u（通过后向边）可指向 v 的真祖先\n",
    "                    hca(v) = min(hca(v), hca(u)); //则 v 亦必如此\n",
    "                else { //否则，以 v 为关节点（u 以下即是一个 BCC，且其中顶点此时正集中于栈 S 的顶部）\n",
    "                    while ( v != S.pop() ) //依次弹出当前 BCC 中的节点，亦可根据实际需求转存至其它结构\n",
    "                        /*pass*/;\n",
    "                    S.push(v); //最后一个顶点（关节点）重新入栈---总计至多两次\n",
    "                }\n",
    "                break;\n",
    "            case DISCOVERED:\n",
    "                type(v, u) = BACKWARD; //标记(v, u), 并按照 “越小越高” 的准则\n",
    "                if (u != parent(v))\n",
    "                    hca(v) = min(hca(v), dTime(u)); //更新 hca[v]\n",
    "                break;\n",
    "            default: //VISITED（有向图）\n",
    "                type(v, u) = (dTime(v) < dTime(u)) ? FORWARD:CROSS;\n",
    "                break;\n",
    "        }\n",
    "    status(v) = VISITED; //对 v 的访问结束\n",
    "}\n",
    "\n",
    "#undef hca\n",
    "```\n",
    "\n",
    "这里只增加了规模为 O(n) 的辅助栈，故整体空间复杂度 O(n+e)。时间上，当每次找到关节点  v 时，发会重复入栈，但此时对应地至少有另一顶点出栈且不再入栈，故整体上关节点的入栈操作累计不会超过 2n 次，整体为 O(n+e)。\n",
    "\n",
    "\n",
    "## 优先级搜索\n",
    "\n",
    "图搜索应用的基本框架都类似，都需通过迭代逐一发现各顶点，将其纳入遍历树中并做相应处理，同时根据应用需求，做相应处理。各算法在功能上的不同，体现在每一步迭代中对新顶点的选取策略不同，如 BFS 搜索会优先考查更早发现的顶点，而 DFS 搜索相反，会优先考查最后被发现的顶点。\n",
    "\n",
    "每种选取策略都等效于给所有顶点赋予不同的优先级，而且随着算法的推进不断调整，而每一步迭代所选取的顶点，都是当时的优先级最高者。因此力搜索框架也称为**优先级搜索(priority-first search, PFS)**，或 **最佳优先搜索(best-first search, BFS)**。\n",
    "\n",
    "顶点的优先级数初始化为一个最大值，如 INT_MAX，表示其优先级最低。\n",
    "\n",
    "\n",
    "```cpp\n",
    "//优先级搜索基本框架\n",
    "template <typename Tv, typename Te> template <typename PU> //优先级搜索（全图）\n",
    "void Graph<Tv, Te>::pfs( int s, PU prioUpdate){ //assert: 0 <= s < n\n",
    "    reset(); int v = s; //初始化\n",
    "\n",
    "    do //逐一检查所有顶点\n",
    "        if (UNDISCOVERED == status(v)) //一旦遇到尚未发现的顶点\n",
    "            PFS(v, prioUpdate); //即从该顶点出发启动一次 PFS\n",
    "    while (s != (v=(++v % n))); //按序号检查，故不漏不重\n",
    "}\n",
    "\n",
    "template <typename Tv, typename Te> template <typename PU> //顶点，边，优先级更新器\n",
    "void Graph<Tv, Te>::PFS(int v, PU prioUpdate){ //优先级搜索（单个连通域）\n",
    "    //初始化\n",
    "    priority(v) = 0;\n",
    "    status(v) = VISITED;\n",
    "    parent(v) = -1; //起点 v 加至 PFS 树中\n",
    "\n",
    "    while(1) { //将下一顶点和边加至 PFS 树中\n",
    "        for (int u=firstNbr(v); -1<u; u=nextNbr(v,u)) //枚举 v 的所有邻居\n",
    "            prioUpdate(this, v, u); //更新顶点 u 的优先级及其父顶点\n",
    "\n",
    "        //从尚未加入遍历树的顶点中选出一个优先级最高的顶点 v\n",
    "        for (int shortest = INT_MAX, u=0; u<n; u++) //n 为顶点总数\n",
    "            if (UNDISCOVERED == status(u))\n",
    "                if (shortest > priority(u)) {\n",
    "                    shortest = priority(u);\n",
    "                    v = u;\n",
    "                }\n",
    "\n",
    "        if (VISITED == status(v)) //直到所有顶点均已加入\n",
    "            break;\n",
    "\n",
    "        status(v) = VISITED; //将 v 及其父的联边加入遍历树\n",
    "        type(parent(v), v) = TREE;\n",
    "    }\n",
    "} //通过定义具体的优先级更新策略prioUpdate, 即可实现不同的算法功能\n",
    "```\n",
    "\n",
    "此前的 BFS 和 DFS 搜索也可基于此模式统一实现。\n",
    "\n",
    "## 最小支撑树\n",
    "\n",
    "**支撑树或生成树 spanning tree**： 连通图 G 的某一无环连通子图，并覆盖 G 中的所有顶点，即 “禁止环路” 前提下的极大子图，也是 “保持连通” 前提下的最小子图。\n",
    "\n",
    "若 G 为一带权网络，每一支撑树的成本即为其各边权重的总和，成本最小者为 **最小支撑树 minimum spanning tree, MST**。\n",
    "\n",
    "最小支撑树不唯一。\n",
    "\n",
    "\n",
    "### 最小支撑树的 Prim 算法\n",
    "\n",
    "基于以下事实：最小支撑树总是会采用联接每一割的最短跨越边。但这并不意味着同一割仅能为最小支撑树贡献一条跨越边。\n",
    "\n",
    "基于贪心算法：每步迭代前，假设已得到最小支撑树 T 的一棵子树 $T_k = (V_k; E_K)$，其中 $V_k$ 含 k 个顶点， $E_K$ 含 $k-1$ 条边。若将 $V_K$ 及其补集视作一个割，则在找到该割的最短跨越边 $e_k$ 后，可将 $T_k$ 扩展为一棵更大的子树 $T_{k+1}$。而迭代基 $T_1$ 为不含边的单个顶点，可在原图中任意选取。\n",
    "\n",
    "\n",
    "```cpp\n",
    "//最小支撑树 Prim 算法\n",
    "template <typename Tv, typename Te> struct PrimPU { //针对 Prim 算法的顶点优先级更新器\n",
    "    virtual void operator() (Graph<Tv, Te>* g, int v, int u) {\n",
    "        if (UNDISCOVERED == g->status(u)) //对于 v 的每一尚未发现的邻接顶点 u\n",
    "            if (g->priority(u) > g->weight(v, u)) { //按 Prim 策略做松弛\n",
    "                g->priority(u) = g->weight(v, u); //更新优先级（数）\n",
    "                g->parent(u) = v; //更新父节点\n",
    "            }\n",
    "    }\n",
    "};\n",
    "```\n",
    "\n",
    "即更新 v 的每一尚未发现的邻接顶点 u 的优先级 priority 的值为边 vu 的权重值 weight。时间复杂度 $O(n^2)$。\n",
    "\n",
    "\n",
    "### 最短路径\n",
    "\n",
    "+ 单调性：设顶点 s 到 v 为最短路径为 p，u 为 p 上的点，则 s 到 u 的其中一条最短路径也即路径 p 上的 s 到 u 部分。 \n",
    "+ 歧义性： 最短路径不唯一。\n",
    "+ 无环性：因为单调性，起点 s 到其余顶点的最短路径的并集，必然不含任何（有向）回路，从而构成 **最短路径树 shortest-path tree**。\n",
    "\n",
    "### 最短路径 Dijkstra 算法\n",
    "\n",
    "类似 Prim, 每次由 $T_k$ 扩展到 $T_{k+1}$ 时，可将 $V_k$ 之外各顶点 u 到 $V_k$ 的距离看到 u 的优先级数。如此，每一最短跨越边所对应的顶点 u，都会因拥有最小优先级数（最高优先级）而被选中。\n",
    "\n",
    "```cpp\n",
    "//最短路径 Dijkstra 算法\n",
    "template <typename Tv, typename Te> struct DijkstraPU { //针对 Dijkstra 算法的顶点优先级更新器\n",
    "    virtual void operator() (Graph<Tv, Te>* g, int v, int u){\n",
    "        if (UNDISCOVERED == g->status(u)) //对于 v 每一尚未被发现的邻接顶点 u, 按 Dijkstra 策略\n",
    "            if (g->priority(u) > g->priority(v)+g->weight(v,u)) { //做松弛\n",
    "                g->priority(u) = g->priority(v) + g->weight(v, u); //更新优先级（数）\n",
    "                g->parent(u) = v; //并同时更新父节点\n",
    "            }\n",
    "    }\n",
    "};\n",
    "```\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 2",
   "language": "python",
   "name": "python2"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 2
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython2",
   "version": "2.7.12"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}
